package com.mystudy.algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 计数排序
 * @author: zhouzhilong
 * @create: 2019-07-31 16:00
 **/
public class CountingSort {
    /**
     * logger
     */
    private static final Logger LOGGER = LoggerFactory.getLogger(CountingSort.class);

    @Test
    public void test() {
        int[] arr = new int[]{4, 1, 9, 5, 1, 9, 5, 6, 6, 9, 2, 15, 21, 96, 34};
        int[] sort = sort(arr);
        LOGGER.debug("sort = [{}]", sort);
    }

    private int[] sort(int[] arr) {
        int max = maxMium(arr);
        int min = minMium(arr);
        int[] result = new int[max - min + 1];
        int step = min;
        for (int i = 0; i < arr.length; i++) {
            result[arr[i] - min]++;
        }
        int count = 0;
        for (int i = 0; i < result.length; i++) {
            while (result[i] > 0) {
                arr[count] = i+min;
                count++;
                result[i]--;
            }
        }
        return arr;
    }


    private int maxMium(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    private int minMium(int[] arr) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        return min;
    }

}
